/*
https://leetcode.cn/problems/count-the-number-of-good-nodes/description/
*/
--------------------------------------------

class Solution {
    // 邻接表的三个数组，用于表示图结构
    int[] h, ne, e;
    int idx, ans; // idx 用于记录当前边的索引，ans 用于累计好节点的数量

    // 添加一条无向边到邻接表中
    void add(int a, int b) {
        e[idx] = b; // 存储边的目标节点
        ne[idx] = h[a]; // 将新边连接到已有边的链表头部
        h[a] = idx++; // 更新头指针，并增加索引
    }

    // 主函数，计算好节点的数量
    public int countGoodNodes(int[][] edges) {
        idx = 0; // 初始化边的索引
        ans = 0; // 初始化好节点计数为0
        int n = edges.length; // 边的数量
        h = new int[2 * n + 10]; // 初始化头指针数组，大小为2*n+10以确保足够大
        ne = new int[2 * n + 10]; // 初始化下一个元素指针数组
        e = new int[2 * n + 10]; // 初始化目标节点数组
        Arrays.fill(h, -1); // 将头指针初始化为-1，表示尚未添加任何边

        // 根据给定的边构建图结构
        for (int[] t : edges) {
            add(t[0], t[1]); // 添加双向边
            add(t[1], t[0]);
        }

        // 从节点0开始进行深度优先搜索
        dfs(0, -1); // -1 表示没有父节点
        return ans; // 返回好节点的数量
    }

    // 深度优先搜索函数，递归地遍历每个节点的子树
    int dfs(int son, int fa) {
        int size = 1; // 记录当前子树的节点个数，初始为1，包括自身
        int pre = 0; // 记录第一个子树的节点数，用于后续比较
        boolean st = true; // 判断是否满足好节点条件的标志，默认为true

        // 遍历与当前节点相连的所有节点
        for (int i = h[son]; i != -1; i = ne[i]) {
            int j = e[i]; // 获取相邻节点
            if (j == fa) { // 如果是父节点，跳过，避免向上搜索
                continue;
            }
            int sz = dfs(j, son); // 递归处理子节点，获取其子树的大小

            // 第一次遇到子树时直接记录其大小
            if (pre == 0) {
                pre = sz;
            } else if (pre != sz) { // 如果不是第一次且子树大小不同，则标记为非好节点
                st = false;
            }
            size += sz; // 累加子树大小到当前子树大小
        }

        // 如果所有子树大小相同，则当前节点是好节点
        if (st)
            ans++;

        return size; // 返回当前子树的大小
    }
}

-----------------------------------------------------